The invention concerns a method to generate a random signal and a random signal generator.
From the xe2x80x98Alpha-particle random number generatorxe2x80x99 IBM TECHNICAL DISCLOSURE BULLETIN, Vol. 30, No.9, February 1988 (1988-02), pages 337-339, XP002140868 IBM CORP. NEW YORK, US ISSN: 0018-8689, a random signal generator is known, that has four non-deterministic random sequence generators, each of them having a feed-back shift register. The shift registers are subjected to alpha radiation of a radioactive material, what generates, when penetrating in the semiconductor chip of the shift register, electron hole pairs, which can randomly change the memory content of the shift register. The outputs of two of the four random sequence generators are connected to the inputs of an exclusive-or gate. The outputs of this exclusive-or gate are connected to an input of a further exclusive-or gate, the output of which is connected to the random signal output. Therefore the random signal fed to the random signal output is generated by means of the exclusive-or gate by mixing the output signals of the individual random sequence generators, resulting in the random signal fed to the random signal output having a stronger random nature than the output signals of the individual random sequence generators. Nevertheless, by these measures the statistical independence of the signal levels or the random values of the random signal appearing at the output of the random signal generator is improved only to a limited extent. Although the quality of the random signal could be improved by that the number of the random sequence generators, the output signals of which are exclusive-or connected with one another, is correspondingly increased, the construction of the random signal generator, however, becomes more complicated and expensive. In addition, the random signal generator has the disadvantage that the alpha-radiation requires an expensive shielding to prevent damages to health and/or interference with other electrical circuits.
From WO 97/43709 a random signal generator is already known that has a non-deterministic random signal generator that has a voltage-controlled oscillator, the frequency control input of which is connected to a noise voltage source. On its output the oscillator has an oscillator signal, the frequency of which randomly fluctuates about a centre frequency corresponding to a stochastically changing noise voltage applied to the frequency control input. The random sequence generator has a plurality dynamic flip-flops, which with their data input are connected to a ring oscillator allocated to them. At the same time each flip-flop has its own ring oscillator, while the frequencies of these ring oscillators slightly deviate from one another and are greater in each case than the frequency of the voltage-controlled oscillator of the random signal generator. Each clock input of the flip-flops is connected to the output of the random signal generator, so that in the case of a clock slope of the oscillation signal of the voltage-controlled oscillator with randomly changing frequency one signal value of the individual oscillation signal of the ring oscillators is scanned and read into the flip-flop allocated to the respective ring oscillator. The signal values intermediately stored in the individual flip-flops are then emitted to a respective output of the flip-flop and form the random signal to be generated. On this occasion each signal fed to the outputs of the flip-flops represents a binary number of a random number to be generated with several digits. According to the patent, the binary values of the digital signals fed to the output of the flip-flops are to be evenly distributed, i.e. on average the outputs of the flip-flop should have an approximately equal number of logical xe2x80x9conesxe2x80x9d and xe2x80x9czerosxe2x80x9d.
The prior known random number generator has, however, the disadvantage that the individual number signals or the binary positions of the random number allocated to them depend, to a certain degree, from one another. It may also result in a correlation of two random numbers which are read out immediately in succession from the random signal generator. Therefore, after a sufficiently long observation of the random numbers emitted by the random number generator, an observer can make conclusions regarding the properties of the random signal generator or random number generator, in particular regarding the properties of the ring oscillators contained therein. An additional disadvantageous fact is that a defect in the noise voltage source and/or in the voltage-controlled oscillator of the random signal generator may result in an oscillation of the voltage-controlled oscillator with a constant frequency, so that the correlation of the random numbers will strongly increase, i.e. the random nature of the random signals or the random numbers represented by this signal will decrease without the user of the random number generator noticing this. For certain applications, for example, when encoding messages or identifying a sender of a message by means of a xe2x80x9cdigitalxe2x80x9d signature, it is, however, necessary that the random nature of the generated signal or of the random numbers be as great as possible so that the random numbers could not be predicted.
From EP 0 782 069 A1 a pseudo-random number generator is known, that has several deterministic random sequence generators, each of them having an output for a pseudo-random signal. These outputs are connected to an input each of a combination device, that has an output for a combination signal formed by non-linear combination of the pseudo-random signals. The combination signal output is connected to the data input of a shift register having a plurality of memory elements, into which the data read out from the combination signal output can be sequentially read. The data outputs of the memory elements of the shift register are connected to an input each of a non-linear connecting device. This has an output for a signal that is formed by the non-linear combination of the data signals applied to the data outputs of the memory elements of the shift register. The individual positions of the random number to be generated are emitted on this output in succession synchronously with a clock signal. The prior known pseudo-random number generator has the disadvantage that the signal appearing on the output of the connecting device can be described by a mathematical function despite the relatively elaborate combination of several pseudo-random signals into a random number signal. Therefore the random numbers, generated with the random number generator, can be predicted with the knowledge of this mathematical function and the state of the random signal generator. An additional disadvantage is that the random signal generator has a relatively complicated construction.
A random signal generator is also known, wherein an analog noise signal of a noise source is amplified with a high-frequency amplifier and subsequently the signal level of this amplifier is digitalised. The random number to be generated is then sequentially read out on the output of the high-frequency amplifier, whereby both signal levels, defined by digitalising the amplifier output signal, are interpreted as binary values of a binary number. This random signal generator is, however, also relatively expensive, because for the purpose of avoiding correlations between the digital output signal of the random number generator and the analog noise signal an elaborate shielding of the high-frequency amplifier is required. In addition, the noise source has to be shielded against external electro-magnetic interferences.
Therefore the task is to specify a method, with which a random signal, that has signal levels or random values which are, as far as possible, statistically independent from one another and uniformly distributed, can be generated. There is also the additional task to provide a random signal generator which, though having a simple construction, can generate as far as possible, statistically independent from one another and uniformly distributed signal levels, random values or random numbers.
Therefore in an advantageous manner random sequence signal values generated at different points of time are exclusive-or connected with one another, by virtue of which an even stronger random nature of the signal levels or random values of the generated random signals is achieved. Consequently a good approximation of a uniform distribution is achieved by the statistical distribution of the signal levels or random values of the generated random signal.
An embodiment of the method provides that the exclusive-or output signal is exclusive-or connected with the random sequence signal of at least one further non-deterministic random sequence generator and the exclusive-or output signal of this connection forms the intermediate signal for further processing. The statistical distribution of the signal levels or random values of the random signal generated is then even better approximated to a uniform distribution.
The above mentioned task regarding the method can be also solved by that at least two random sequence signals are generated by means of at least two non-deterministic random sequence generators,
a) that one random signal value is determined from each random sequence signal of the individual random sequence generators and is exclusive-or connected to a stored value allocated to another random sequence generator,
b) the result of this connection is intermediately stored on each occasion as new stored value, allocated to the first-mentioned random sequence generator,
c) that steps a) and b) of the method are repeated at least once more as a loop,
d) and that afterwards the stored values allocated to each individual random sequence generator are emitted as random signal.
Consequently a plurality of random sequence signals is generated with the aid of various random sequence generators, wherein these random sequence signals are combined with one another by means of exclusive-or connections corresponding to steps a) to d) of the method. In an advantageous manner a random signal can be generated by this method which has a greater random nature than the individual random sequence signals from which the random signal was mixed. Therefore the method makes it feasible to determine random numbers or random signals which are practically not correlated with one another and occur almost uniformly distributed by means of several relatively simply constructed random signal generators.
It is of advantage if the steps a) to d) of the method are repeated several times. This makes it possible to generate random numbers which have a greater number of digits or positions than the number of the random signal generators.
It is of advantage if the stored values are cyclically shifted in a data memory. In that case the random signal values generated by means of individual random sequence generators can be mixed even better.
It is particularly advantageous if the random sequence generators are reset to a defined condition or state before each renewed running of step a) of the method. Due to this, the correlation of the two signal values of the random signal determined in immediate succession can be additionally reduced.
A preferred embodiment of the method provides that for the generation of random sequence signals of the random sequence generators the frequency of each voltage-controlled oscillator is altered by means of a noise voltage signal and that the random signal value is determined from each oscillator signal of the oscillator. Consequently, the random signals can be generated in a simple manner already with a relatively good uniform distribution of their random signal values.
It is particularly advantageous if there is a delay of a defined period, that is equal to or greater than the period of the oscillator signal, before each renewed running of step a) of the method. The delay can be greater, for example, than ten times the period. Random signal values or random numbers determined successively or consecutively from the random signal have in this case an even lower correlation between them.
The above mentioned task regarding the random signal generator is solved with the features of patent claim 10.
By this it is possible random sequence signal values generated at different points of time are exclusive-or connect with one another, by virtue of which an even stronger random nature of the signal levels or random values of the generated random signals is achieved. The random signal generated by the random signal generator has a stronger random nature than the individual random sequence signals from which the random signal was mixed. Thus, even when using random sequence generators of simple construction, a good approximation of a uniform distribution can be achieved with the statistical distribution of the signal levels or random values of the random signal generated.
It is of advantage if at least one of the further intermediate stage has an exclusive-or gate, one input of which is connected to the output of the exclusive-or gate connected to the random sequence generators and the other input to the random sequence signal output of a further random sequence generator. In this case the statistical distribution of the signal levels or random values approximate a uniform distribution of the random signals generated with the random signal generator even better.
The above mentioned task regarding the random signal generator can be solved also by that the random signal generator has at least two functional groups, each of which has a non-deterministic random sequence generator, an exclusive-or gate and a memory element, wherein one of the two inputs of the exclusive-or gate of each functional group is connected to a random sequence signal output of the random sequence generator of the functional group and the other input to a data output of the memory element of the functional group, wherein the output of the exclusive-or gate of each functional group is connected to the data input of the memory element of the functional group, and wherein the memory elements of the functional groups are connected to one another via data lines for the purpose of shifting their memory contents.
Therefore in an advantageous manner each signal value of the random signal to be generated is formed from the random signal values of several, preferably of all random sequence generators, due to which the signal values of the random signal have a stronger random nature than the random signal values determined from the random sequence signals of the random sequence generators. Accordingly, the random signal generator makes it possible to determine random signals with almost perfectly uniformly distributed random nature of their signal values, even when the random nature of the random sequence signal values of the individual random sequence generators deviates from the ideal uniform distribution, as this is always the case in practice. In addition, random signal values determined successively with the random signal generator, exhibit only a very weak correlation. Therefore the individual random sequence generators of the random signal generator can have a relatively simple construction, resulting in a random signal generator having an overall simple construction that is economical to manufacture. In an advantageous manner in the case of a random signal generator, that has more than two random sequence generators, a good uniform distribution of the random nature of the random signal values and a weak correlation between the individual random signal values can be achieved even when one of the random sequence generators fails or when for other reasons, e.g. environmental influences (temperature, electromagnetic fields, manipulation attempts, etc.) and/or ageing processes, the random nature of the random sequence signal values is lost. Therefore the random signal generator is highly reliable in its operation.
The above mentioned task regarding the random signal generator can be solved also by that the random signal generator has at least two functional groups, each of them having a random sequence generator, an exclusive-or gate and a memory element, wherein one of the two inputs of the exclusive-or gate of each functional group is connected to a random sequence signal output of the random sequence generator of the functional group and the other input to a data output of the memory element of another functional group, and wherein the output of the exclusive-or gate is connected to the data input of the memory element of the first-mentioned functional group.
This invention also provides the advantage that additional data lines for shifting the memory contents between the memory elements can be omitted.
An embodiment of the invention provides that the memory element or the memory elements are part of a ring shift register. In this case, after each exclusive-or connection of the random signal values to the memory contents, the memory contents of the memory elements can be cyclically shifted in the ring memory in a simple manner. At the same time it is even possible for the ring shift register to have intermediate memory elements in addition to the memory elements of the functional groups. In this case additional digits of a random number to be determined can be intermediately stored in the intermediate memory elements. The number of digits or positions of the individual random numbers can be then greater than the number of the random sequence generators of the random signal generator.
It is particularly advantageous if the random signal generators have a reset input, by means of which the random signals of the random sequence generators can be transferred to a defined state. The random sequence generators can be then brought to a defined output state before determining a new random number, thus reducing the correlation between consecutively determined random numbers.
In the case of a preferred embodiment of the invention the random sequence generators have a voltage-controlled oscillator each, the frequency control input of which is connected to a noise voltage source, wherein the oscillator output is connected to the random sequence signal output of the random sequence generator. By virtue of this the random sequence signals can be generated in a simple manner and with a relatively good uniform distribution of the random nature of their random sequence signal values.
It is of advantage if the oscillator output is connected to the input of a flip-flop or a kind of frequency divider and if the output of the flip-flop is connected to the random sequence signal output of the random sequence generator. The flip-flop then inverts its output signal with every clock pulse of the oscillator, due to which a better uniform distribution of the random signal values obtained from the random signal present on the output of the random signal generator is achieved.
Particularly advantageous is if at least the exclusive-or gate(s) and possibly the ring shift register are part of a microprocessor. The random signal generator can be then particularly cost-effectively produced and constructed, for example, as an insertion card that has a bus terminal for the connection to the system bus of a microcomputer.